package leetCode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * TODO
 *
 * @author 司松坡
 * @createTime 2023年03月20日
 */
public class LeetCode40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] bool = new boolean[candidates.length];
        int site = 0;
        Arrays.sort(candidates);
        combination(res, candidates, new ArrayList<>(), target, bool, site);
        return res;
    }

    public void combination(List<List<Integer>> res, int[] candidates, List<Integer> instantly, int target, boolean[] bool, int site) {
        if (target == 0) {
            if (!res.contains(instantly)) {
                res.add(new ArrayList<>(instantly));
            }
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = site; i < candidates.length; i++) {
            if (target - candidates[site] < 0) {
                break;
            }
            if (!bool[i]) {
                bool[i] = true;
                instantly.add(candidates[site]);
                if (candidates[i] == candidates[i - 1] && i > site) {
                    continue;
                }
                combination(res, candidates, instantly, target - candidates[site], bool, i+1);
                bool[i] = false;
                instantly.remove(instantly.size() - 1);
            }
        }
    }

    @Test
    public void test() {
        List<String> strings = new ArrayList<>();
        strings.add("asd");
        System.out.println(strings.subList(0,1));
    }


}
